//  MSD  最大百位的情况下
#include <iostream>

using namespace std;

#define MAXSIZE 10000

int getdigit(int x, int d)
{
	int a[] = {1, 1, 10, 100};
	return (x/a[d])%10;
}

void PrintArr(int ar[], int n)
{
	for (int i = 0; i<n; ++i)
		cout<<a[i]<<" ";
	cout<<endl;
}

void mdsradix_sort(int arr[], int begin, int end, int d)
{
	const int radix =  10;
	int count[radix], i, j;
	for(i = 0; i<radix; ++i)
	{
		count[i] = 0;
	}

	int *bucket = (int*)malloc((end-begin+1)*sizeof(int));
	for(i = begin; i<=end; ++i)
	{
		count[getdigit(arr[i],d)]++;
	}
	for(i = 1; i< radix; ++i)
	{
		count[i]=count[i]+count[i-1];
	}
	for(i = end; i>=begin; --i)
	{
		j = getdigit(arr[i], d);
		bucket[count[j]-1] = arr[i];
		--count[j];
	}
	for(i = begin, j = 0; i <= end; ++i, ++j)
	{
		arr[i] = bucket[j];
	}
	free(bucket);
	

}


int main()
{
    cout << "Hello world!" << endl;
    return 0;
}